/**
 * 冒泡
 * 稳定
 * time:O(n*n)
 * space: o(1)
*/ 


function maopao(arr){
    const length = arr.length
    for(let i = 0; i < length; i++){
        for(let j = 0; j < length -i; j++){
            if(arr[j] > arr[j+1]){
                [arr[j],arr[j+1]] = [arr[j+1],arr[j]]
            }
        }
    }
    return arr
}

// console.log(maopao([2,5,1,6,4,7,9,2]))

/**
 * 选择排序
 * 不稳定
 * o(n*n)
 * o(1)
 */

function selectSort(arr){
    const length = arr.length

    for(let i = 0; i < length; i++){
        let count = i
        for(let j = i; j < length; j++){
            if( arr[j] < arr[count]){
                count = j
            }
        }
        [arr[i],arr[count]] = [arr[count], arr[i]]
    }

    return arr
}

// console.log(selectSort([2,5,1,6,4,7,9,2]))

/**
 * 快排
 * time: nlogn
 * space: o(1)
 */

function findBase(arr,start,end){
    const point = arr[start]
    let i = start + 1,
        j = end
    while(j >= i){
        if(point > arr[i]){
            i++
        }else if(point <= arr[j]){
            j--
        }else{
            [arr[i],arr[j]] = [arr[j],arr[i]]
            i++;
            j--;
        }
    }
    [arr[start], arr[i-1]] = [arr[i-1],arr[start]]

    return i-1

}

function sort(arr,start,end){
    const base = findBase(arr,start,end)
    if(start<end){
        sort(arr, start, base-1)
        sort(arr, base+1, end)
    }
}

function fastSort(arr){
    sort(arr,0,arr.length-1)
    return arr
}

//console.log(fastSort([2,5,1,6,4,7,9,2]))


/**
 * 归并排序
 * time: nlog(n)
 * space: O(n)
 */

function mergeSort(arr){
    const length = arr.length;
    if(length < 2){
        return arr
    }
    const mid = Math.floor(length/2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    return merge(left, right);
}

function merge(left, right){
    let i = 0, j = 0;
    // 定义一个空数组，用来存放合并后的数组
    const result = [];
    // 比较两个数组的第一个元素，将较小的放入result数组
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }
    // 将没有比较完的剩余元素放入result数组
    while (i < left.length) {
        result.push(left[i++]);
    }
    while (j < right.length) {
        result.push(right[j++]);
    }
    // 返回合并后的数组
    return result;
}

console.log(mergeSort([2,5,1,6,4,7,9,2]))


/**
 * 堆排序
 * time: O(n)
 * space 
 */